package niuKe;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class V016_购物单 {
    //题目描述
    //王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：
    // 主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
    //主件	附件
    //电脑	打印机，扫描仪
    //书柜	图书
    //书桌	台灯，文具
    //工作椅	无
    //如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。每个主件可以有 0 个、 1 个或 2 个附件。
    //附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，
    //分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。
    //他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
    //设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：
    //v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 为乘号）
    //请你帮助王强设计一个满足要求的购物单。
    //
    //输入描述:
    //输入的第 1 行，为两个正整数，用一个空格隔开：N m
    //
    //（其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）
    //从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
    //（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。
    // 如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
    //输出描述:
    //输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。
    //示例1
    //输入
    //1000 5
    //800 2 0
    //400 5 1
    //300 5 1
    //400 3 0
    //500 2 0
    //输出
    //2200

    //50 5
    //20 3 5
    //20 3 5
    //10 3 0
    //10 2 0
    //10 1 0
    //输出
    //130
    //说明：
    //由第1行可知总钱数N为50以及希望购买的物品个数m为5；
    //第2和第3行的q为5，说明它们都是编号为5的物品的附件；
    //第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5；
    //所以物品的价格与重要度乘积的总和的最大值为10*1+20*3+20*3=130
    public static int dw=100;
    public static void main(String[] args) throws IOException {
        boolean flag=true;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] strArr=br.readLine().split(" ");
        int N = Integer.parseInt(strArr[0]); //总钱数
        int m = Integer.parseInt(strArr[1]); //想买得物品数量
        good[] A = new good[m+1];
        for(int i=1;i<=m;i++){
            strArr = br.readLine().split(" ");
            int v = Integer.parseInt(strArr[0]); //价格
            int p = Integer.parseInt(strArr[1]); //重要程度
            int q = Integer.parseInt(strArr[2]); //主附件（附件归属主件编号）
            if (flag){
                if(v%dw!=0){
                    flag = false;
                    dw=10;
                    //如果有物品没有到百元 则之前的物品乘10，所有物品按除10计算
                    for(int j=1;j<i;j++)
                        A[j].setV(A[j].v*10);
                }
            }
            v=v/dw;  //除100或10提升计算速度
            A[i]=new good(v,p,q);

        }

        for(int i=1;i<=m;i++){
            int q = A[i].q;
            if(q>0){
                //如果是附件的话 先判断是主件的第几个附件 再把附件对应的行数i赋给它 后面可以直接通过A[i]的a1、a2获取附件v、p
                if(A[q].a1==0){
                    A[q].setA1(i);
                }else{
                    A[q].setA2(i);
                }
            }
        }
        N=N/dw;
        for (good good : A) {
            if(null!=good) System.out.println(good.toString());
        }
        dp(N,A);
    }
    public static void dp(int N,good[] A){
        int[][] dp = new int[N+1][A.length];

        for(int i=1;i<A.length;i++){
            int v=-1,v1=-1,v2=-1,v3=-1,tempdp=-1,tempdp1=-1,tempdp2=-1,tempdp3=-1;
            v=A[i].v;
            tempdp=v*A[i].p;
            if(A[i].a1!=0&&A[i].a2!=0){
                //通过A[i]的a1、a2获取附件v、p
                v3=v+A[A[i].a1].v+A[A[i].a2].v;
                tempdp3=tempdp+A[A[i].a1].v*A[A[i].a1].p+A[A[i].a2].v*A[A[i].a2].p;
            }
            if(A[i].a1!=0){
                v1 = v + A[A[i].a1].v;
                tempdp1=tempdp+A[A[i].a1].v*A[A[i].a1].p;
            }
            if(A[i].a2!=0){
                v2 = v + A[A[i].a2].v;
                tempdp2=tempdp+A[A[i].a2].v*A[A[i].a2].p;
            }
            for(int j=1;j<N+1;j++){
                if(A[i].q>0){
                    dp[j][i]=dp[j][i-1];
                }else{
                    dp[j][i]=dp[j][i-1];
                    //每组有四种情况:a.主件，b.主件+附件，c.主件+附件,d.主件+附件1+附件2
                    if(j>=v&&v!=-1) dp[j][i] = Math.max(dp[j][i],dp[j-v][i-1]+tempdp);
                    if(j>=v1&&v1!=-1) dp[j][i]=Math.max(dp[j][i],dp[j-v1][i-1]+tempdp1);
                    if(j>=v2&&v2!=-1) dp[j][i]=Math.max(dp[j][i],dp[j-v2][i-1]+tempdp2);
                    if(j>=v3&&v3!=-1) dp[j][i]=Math.max(dp[j][i],dp[j-v3][i-1]+tempdp3);
                }
            }

        }
        for (int[] ints : dp) {
            for (int anInt : ints) {
                System.out.print(anInt+" ");
            }
            System.out.println();
        }
        System.out.println(dp[N][A.length-1]*dw);
    }


}


class good{

    int v;
    int p;
    int q;
    int a1=0;
    int a2=0;

    good(int v,int p,int q){
        this.v=v;
        this.p=p;
        this.q=q;
    }
    public void setV(int v){
        this.v=v;
    }
    public void setA1(int a1){
        this.a1=a1;
    }
    public void setA2(int a2){
        this.a2=a2;
    }

    @Override
    public String toString() {
        return "v="+v+
        " p="+p+
        " q="+q+
        " a1="+a1+
        " a2="+a2;
    }
}
